#
# @lc app=leetcode.cn id=144 lang=python3
#
# [144] 二叉树的前序遍历
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    outList = []
    def preorderTraversal(self, root: TreeNode) -> List[int]:
    #solution1:递归法
    #     Solution.outList = []
    #     if root != None:
    #         self.midOrder(root)

    #     return Solution.outList    
        
    # def midOrder(self,treeNode):
    #     Solution.outList.append(treeNode.val)
    #     if treeNode.left != None:
    #         self.midOrder(treeNode.left)
        
    #     if treeNode.right != None:
    #         self.midOrder(treeNode.right)
    
    
    #solution2:迭代法
        if root == None: return [] 
        nodeQueue = []
        nodeQueue.append(root)
        Solution.outList = []
        while nodeQueue != []:
            curNode = nodeQueue.pop(0)
            Solution.outList.append(curNode.val)
            if curNode.right != None:
                nodeQueue.insert(0,curNode.right)
            if curNode.left != None:
               nodeQueue.insert(0,curNode.left)
        
        return Solution.outList
            
                
    
    
# @lc code=end

